1. Field of the Invention
The present invention relates to a document-inclination detector, and more particularly to a document-inclination detector that detects the inclination of an input image in a digital image processor, such as an optical character reader (OCR), which processes a document image in a page unit. The xe2x80x9cdocument imagexe2x80x9d means document data in a form of electronic image obtained by reading out the original which is a printed material by use of an image scanner or the like.
2. Description of the Related Art
For example, in processing a document image using an is OCR, there are cases where the input image inclines, for example, due to the inclination of the original with respect to an image scanner that reads the document image. To accurately perform character recognition and the like on the inclined document image as well, the inclination of the input image needs to be corrected, or taking the inclination into consideration becomes necessary in the subsequent processes. For this reason, the inclination of a document image is detected.
As a method of detecting the inclination of a document image, (1) a method which rotates a document image for each very small angle to obtain a marginal distribution and takes the angle of rotation as the inclination of the manuscript when the distribution is the sharpest (Research Report for Institute of Electronics and Communication Engineers of Japan (IECE), PRL 80-70, pp. 9-16), (2) a method which calculates a space distribution for characters or character strings of an original using a two-dimensional Fourier transformation and estimates the angle of inclination from the space distribution (Thesis Journal for IECE, 1984/11, Vol. 670, No. 9, pp. 1044-1051), (3) a method which divides a document image into a plurality of parallel strip areas substantially perpendicular to the line direction, calculates a partial marginal distribution for each strip area, and detects the angle of inclination from the phase shift among the peak points of the marginal distributions for adjacent strip areas (Thesis Journal for IECE, 1983/1, Vol. J66-D, No. 1, pp. 111-118), etc., have been proposed.
Furthermore, a technique that calculates the sum of the absolute values of differences between density cumulated values appearing on adjacent scanning lines in a marginal distribution obtained by the scanning operation in the direction substantially perpendicular to the line direction of the document original and corrects the inclination so that the sum becomes maximum (Japanese Patent Publication Nos. 62(1987)-52337 and 63(1988)-25391), a technique that divides a document image into strip areas with two or more widths, obtains images projected to the strip areas, and detects the angle of inclination from a difference between the widths of the strip areas and from a variation between the projected images (Japanese Unexamined Patent Publication No. 63(1988)-292382), a technique that puts a character into graphical representation by the circumscribed rectangular or marginal distribution and detects the inclination of the graphically represented character array from the relation of array position adjacent to the area of the graphically represented character (Japanese Unexamined Patent Publication No. 2(1990)-44486), a technique that extracts marginal distributions from a plurality of parts of a character string, estimates the position of the character string from each marginal distribution, and estimates the inclination of the entire character string (Japanese Unexamined Patent Publication No. 3(1991)-212780), etc., are known.
In the aforementioned methods, however, complicated processes, which consume time, such as the image rotating process and the two-dimensional Fourier transformation, are needed. Also, the process of calculating a great number of marginal distributions and comparing them is needed, and because of simplification of this process, there is a problem that accuracy of inclination detection will be reduced.
In addition, in the case where the line direction of an original, i.e., vertical or horizontal writing, is known in advance, some of the principles of detection are applicable, but with respect to an original whose line direction of a character string is unknown and an original including both vertical writing and horizontal writing, the phase shift between partial marginal distributions become obscure and in some of the methods the detection of inclination becomes difficult. Furthermore, some of the methods are not applicable because the characteristics of the marginal distribution varies between a Japanese document original and an alphabetic document original, and in other methods, errors in the detection of inclination will become serious.
In view of the foregoing observations and description, the primary object of the present invention is to provide a document-inclination detector which is capable of detecting the inclination of a document image in Japanese and European languages at high speeds with a high degree of accuracy, regardless of whether the originals are written horizontally or vertically.
To achieve the aforementioned object and in accordance with the present invention, there is provided a document-inclination detector comprising
marginal distribution extraction means which divides an input document image into a plurality of small areas by a plurality of vertical dividing lines and extracts a horizontal marginal distribution obtained by projecting each small area in a horizontal direction and also divides the input document image into a plurality of small areas by a plurality of horizontal dividing lines and extracts a vertical marginal distribution obtained by projecting each small area in a vertical direction, the horizontal marginal distribution being constituted by histograms obtained by projecting character strings of the document image in the horizontal direction and the vertical marginal distribution being constituted by histograms obtained by projecting the character strings in the vertical direction,
line-direction detection means which detects a line direction of the document image by comparing the horizontal marginal distribution and vertical marginal distribution extracted by the marginal distribution extraction means,
marginal distribution correction means which corrects the histograms of the marginal distribution projected in the same direction as the line direction detected by the line-direction detection means, and
inclination detection means which detects inclination of the document image from a phase shift between the corrected histograms adjacent to each other.
Therefore, detection of inclination can be performed, whether an original is written vertically or horizontally. By correcting only the histograms of the marginal distribution projected in the direction required for inclination detection and detecting inclination, the process can be simplified. Furthermore, since each histogram of the marginal distribution is corrected, for example, in view of the characteristics of an alphabetic character string, the inclination of an alphabetic document image as well as a Japanese document image can be detected with a high degree of accuracy, and the judgement of the line direction and the detection of the inclination can be generally performed synthetically at high speeds with a high degree of accuracy.
Particularly, the complexity of the inclination detection of a document image has been improved, by employing a simple method of detection which extracts the partial marginal distributions for the character strings of the document image and detects the inclination of the document image from the phase shift between the corrected histograms adjacent to each other. Moreover, in the case where information on the line direction of an original is not given, or in the case where an original includes both vertical writing and horizontal writing, the detection of the line direction is performed before detecting the inclination and only the marginal distribution data in the detected line direction is employed. In this way, further simplification of the inclination detection can be achieved.
In a preferred form of the present invention, the line-direction detection means compares the number of histograms between periodic blanks in the horizontal marginal distribution with the number of histograms between periodic blanks in the vertical marginal distribution and judges that the projection direction of the marginal distribution in which the number of histograms between periodic blanks is greater is the line direction. Also, the line-direction detection means may compare the number of periodic blanks in the horizontal marginal distribution with the number of periodic blanks in the vertical marginal distribution and may judge that the projection direction of the marginal distribution in which the number of periodic blanks is greater is the line direction. Therefore, a judgement of the line direction suitable for inclination detection can be made with respect to an original, including both vertical writing and horizontal writing.
In another preferred form of the present invention, the inclination detection means detects the inclination of the document image from the inclination of a straight line linking the central points of a plurality of the corrected histograms belonging to the same character string. Therefore, the inclination detection can be performed accurately at high speeds. Also, the inclination detection means may detect the inclination of the document image from the inclination of a straight line linking the central points of the corrected histograms belonging to a plurality of character strings. In this case, inclination is detected based on as many corrected histograms as possible over a plurality of character strings. As a result, more accurate results are obtainable.
In still another preferred form of the present invention, the marginal distribution correction means performs a threshold detection (clipping process) on an end portion of each histogram of the marginal distribution projected in the same direction as the line direction, thereby removing the end portion when a level on the end portion is less than a predetermined threshold value. Therefore, with respect to an alphabetic document, in which letters are not uniform in size, a high degree of inclination detection can be performed, the same as for a Japanese document.